Session 4 : Graphs

Creating Graphs

The function Graph[ ] creates a graph. Graphs are created from Lists of edges (and maybe vertices). Directed Edges can be created with the function DirectedEdge[v,w], Undirected edges with UndirectedEdge[v,w]. Edges can also be entered using the shortform v -> w and v <-> w . The vertices may be any expressions (numbers or unset variables in general.
Graph[ edgelist ] creates a graph from the edge list creating all vertices automatically.
Graph[ vertexlist, edgelist] creates a graph with specified edges and vertices

(* Create edges *)
DirectedEdge[v,w]
UndirectedEdge[v,w]
(* Creates a directed graph *)
Graph[{1->2,2->3,1->3,3->4,2->5, 5->1}]
(* Creates an undirected graph with vertices 1,2,3,4,5 *)
Graph[{1,2,3,4,5},{1<->2,2<->3,3<->4,4<->1}]

Labels, Weights, Styles

Vertex and Edge Labels/Edge Weights

Using the options VertexLabels and EdgeLabels assigns labels, the function EdgeWeights assigns weights to edges that can be used for various algorithms or for display. The Labels-Options expect a list of rules that assign to every vertex/edge a label or a global option. The EdgeWeight option expects a list of EdgeWeights.
If the variable g is a Graph object, then using Graph[ g ] creates a copy of that graph (maybe with additional options).

(* Creates a graph with Names as Labels. The Edge Labels are displayed as Tooltip *)
g=Graph[{1->2,2->3,3->1},VertexLabels->Automatic, EdgeLabels->Placed["Name", Tooltip]]
(* Creates a copy of the above graph assigning weights to the edges and using these weights as labels *)
weightedgraph=Graph[g,EdgeWeight->{1,42,-3},EdgeLabels->"EdgeWeight"]
(* The weights are for example used in the adjacency matrix *)
WeightedAdjacencyMatrix[weightedgraph]//MatrixForm

Styles

Graphs can be customized by using styles. Styles can be assigned to Vertices and Edges, either on creation or as options. To combine different styles, use the function Directive[ ]

(* Create a graph with a red vertex, and a green thick edge *)
Graph[{1,Style[2,Red]},{Style[1->2,Directive[Thick,Green]]}, VertexLabels->Automatic]
(* Create a graph, assign edge styles as options. The EdgeStyle option expects a list of rules assigning styles to edges *)
Graph[{1->2,2->3,3->4,4->5,5->6},EdgeStyle->{(1->2)->Thick ,(3->4)->Thick,(5->6)->Thick}, EdgeLabels->"Name"]

Basic Graph Properties

g= Graph[{s->v,s->w,v->w,v->t,w->t},EdgeWeight->{2,1,1,2,3},EdgeLabels->"EdgeWeight"]
(* Vertex and Edge Sets *)
VertexList[g]
EdgeList[g]
VertexCount[g]
EdgeCount[g]

(* Graph Matrices *)
AdjacencyMatrix[g] // MatrixForm
Γ =IncidenceMatrix[g];
Γ//MatrixForm
(* Compute weighted Laplacian matrix of the graph *)
Γ.DiagonalMatrix[{2,1,1,2,3}].Transpose[Γ]//MatrixForm

Graph Functions

g= Graph[{s->v,s->w,v->w,v->t,w->t},EdgeWeight->{2,2,1,2,3},EdgeCapacity->{2,2,1,2,3},EdgeLabels->"EdgeWeight", VertexLabels->Automatic]
(* Finds the shortest path (using edge weights as lengths *)
FindShortestPath[g,s,t]
(* Finds the maximal flow (using edge capacities as capacities *)
FindMaximumFlow[g,s,t]